package com.buddy.leetcode._06;

import java.util.ArrayList;
import java.util.List;

/**
 * Z字形变换
 */
public class ZigZagConversion {

    /**
     * 按行访问
     *  0           6           12
     *  1       5   7       11  13
     *  2   4       8   10      14
     *  3           9           15
     *
     *  假设，总行号数 n，从第0行开始，行号记为 row
     *  每行的索引分别为 k
     *  原字符串的索引为 i: 0 < i < s.length
     *  得出：
     *      第0行位置k处的索引 i = k(2 * n - 2)
     *      最后一行位置k处的索引i=k(2 * n-2)+(n - 1) = k(2 * n -2)+ row
     *      中间行，第row行的
     *          k(2 * n-2)+row (从第0行计算)   以及  k(2 * n-2）+（n-1)+(n - row -1) = (k+1)(2 * n -2) - row
     * @param s 原字符串
     * @param numRows 总行数 ，如果总行数为4，那么行号为0，1，2，3
     * @return 转换后的字符串
     */
    public String convert(String s, int numRows) {
        if (numRows == 1) return s; //如果总行数 = 1，则不用处理，直接返回即可
        int length = s.length();//字符串的总长度
        int cycleLen = 2 * numRows - 2;//总结出来的一个变量

        StringBuilder result = new StringBuilder(length);

        for (int row = 0; row < numRows; row ++) {//row是行数，从0开始，小于总行数
            for (int k = 0; k + row < length ; k += cycleLen) {//k 某行的索引
                result.append(s.charAt(k + row));
                //如果不是第0行也不是最后一行，
                if (row != 0 && row != numRows - 1 && k + cycleLen - row < length)
                    result.append(s.charAt(k + cycleLen - row));
            }
        }
        return result.toString();
    }

    /**
     *思路
     * 通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。
     */
    public String convert_02(String s, int numRows) {

        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++)
            rows.add(new StringBuilder());
        int curRow = 0;
        boolean goingDown = false;
        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }
        StringBuilder ret = new StringBuilder();
        for (StringBuilder row : rows) ret.append(row);
        return ret.toString();
    }
}
